@article{Dubhashi,
  author    = {Devdatt P. Dubhashi and
               Alessandro Mei and
               Alessandro Panconesi and
               Jaikumar Radhakrishnan and
               Aravind Srinivasan},
  title     = {Fast distributed algorithms for (weakly) connected dominating
               sets and linear-size skeletons},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {71},
  number    = {4},
  year      = {2005},
  pages     = {467-479},
  ee        = {http://dx.doi.org/10.1016/j.jcss.2005.04.002},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{ghaffari,
author = {Mohsen Ghaffari},
title = {Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set},
booktitle = {ICALP},
year = {2014}
}

@article{avin,
  author    = {Chen Avin and
               Yuval Lando and
               Zvi Lotker},
  title     = {Radio cover time in hyper-graphs},
  journal   = {Ad Hoc Networks},
  volume    = {12},
  year      = {2014},
  pages     = {278-290},
  ee        = {http://dx.doi.org/10.1016/j.adhoc.2012.08.010},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@book{wasserman,
author = {S. Wasserman and K. Faust},
title = {Social network analysis: Methods and Applications},
publisher = {Cambridge University Press},
year = {1994}
}

@article{aravind1,
  author    = {Hadas Shachnai and
               Aravind Srinivasan},
  title     = {Finding Large Independent Sets in Graphs and Hypergraphs},
  journal   = {SIAM J. Discrete Math.},
  volume    = {18},
  number    = {3},
  year      = {2004},
  pages     = {488-500},
  ee        = {http://dx.doi.org/10.1137/S0895480102419731},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{aravind2,
author = {I.O. Bercea and N. Goyal and D.G. Harris and A. Srinivasan},
title = {On computing maximal independent sets of hypergraphs in parallel},
booktitle = {SPAA},
year = {June, 2014}
}

@article{Luczak,
  author    = {Tomasz Luczak and
               Edyta Szymanska},
  title     = {A Parallel Randomized Algorithm for Finding a Maximal Independent
               Set in a Linear Hypergraph},
  journal   = {J. Algorithms},
  volume    = {25},
  number    = {2},
  year      = {1997},
  pages     = {311-320},
  ee        = {http://dx.doi.org/10.1006/jagm.1997.0884},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{karp-ram,
author = {Richard M. Karp and Vijaya Ramachandran},
title =  {Parallel algorithms for shared-memory machines},
journal ={In Handbook of Theoretical Computer Science (Vol. A)},
pages = {869-942},
year = {1990}
}

@article{Luby86,
  author    = {Michael Luby},
  title     = {A Simple Parallel Algorithm for the Maximal Independent
               Set Problem},
  journal   = {SIAM J. Comput.},
  volume    = {15},
  number    = {4},
  year      = {1986},
  pages     = {1036-1053},
  ee        = {http://dx.doi.org/10.1137/0215074},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  note		= {Announced at STOC 1985}
}

@article{MetivierRSZ11,
  author    = {Yves M{\'e}tivier and
               John Michael Robson and
               Nasser Saheb-Djahromi and
               Akka Zemmari},
  title     = {An optimal bit complexity randomized distributed MIS algorithm},
  journal   = {Distributed Computing},
  volume    = {23},
  number    = {5-6},
  year      = {2011},
  pages     = {331-340},
  ee        = {http://dx.doi.org/10.1007/s00446-010-0121-5},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{makino,
  author    = {Kazuhisa Makino and
               Tiko Kameda},
  title     = {Efficient generation of all regular non-dominated coteries},
  booktitle = {PODC},
  year      = {2000},
  pages     = {279-288}
}


@article{KarpUW88,
  author    = {Richard M. Karp and
               Eli Upfal and
               Avi Wigderson},
  title     = {The Complexity of Parallel Search},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {36},
  number    = {2},
  year      = {1988},
  pages     = {225-253},
  ee        = {http://dx.doi.org/10.1016/0022-0000(88)90027-X},
  bibsource = {DBLP, http://dblp.uni-trier.de}, 
  note		= {Announced at STOC 1985 and FOCS 1985}
}


@inproceedings{BeameL90,
  author    = {Paul Beame and
               Michael Luby},
  title     = {Parallel Search for Maximal Independence Given Minimal Dependence},
  booktitle = {SODA},
  year      = {1990},
  pages     = {212-218},
  ee        = {http://dl.acm.org/citation.cfm?id=320176.320200},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

  crossref  = {DBLP:conf/soda/1990},


@inproceedings{Kelsen92,
  author    = {Pierre Kelsen},
  title     = {On the Parallel Complexity of Computing a Maximal Independent
               Set in a Hypergraph},
  booktitle = {STOC},
  year      = {1992},
  pages     = {339-350},
  ee        = {http://doi.acm.org/10.1145/129712.129745},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

  crossref  = {DBLP:conf/stoc/STOC24},
  
  
@book{AlonS08book,
  title={The Probabilistic Method},
  author={Alon, N. and Spencer, J.H.},
  isbn={9780470277317},
  series={Wiley Series in Discrete Mathematics and Optimization},
  url={http://books.google.co.jp/books?id=V8YgNioxF6AC},
  year={2008},
  publisher={Wiley}
}


@article{LinialS93,
  author    = {Nathan Linial and
               Michael E. Saks},
  title     = {Low diameter graph decompositions},
  journal   = {Combinatorica},
  volume    = {13},
  number    = {4},
  year      = {1993},
  pages     = {441-454},
  ee        = {http://dx.doi.org/10.1007/BF01303516},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@COMMENT = {copied from leaderelect.bib}


@article{higham, 	
author = {Karl R. Abrahamson and Andrew Adler and Lisa Higham and David G. Kirkpatrick},
title ={Tight Lower Bounds for Probabilistic Solitude Verification on Anonymous Rings},
journal = {J. ACM},
volume =  {41(2)},
pages = {277-310},
year =  {1994}
}

@article{Nygren-Akamai,
    abstract = {{Comprising more than 61,000 servers located across nearly 1,000 networks in 70 countries worldwide, the Akamai platform delivers hundreds of billions of Internet interactions daily, helping thousands of enterprises boost the performance and reliability of their Internet applications. In this paper, we give an overview of the components and capabilities of this large-scale distributed computing platform, and offer some insight into its architecture, design principles, operation, and management.}},
    address = {New York, NY, USA},
    author = {Nygren, Erik and Sitaraman, Ramesh K. and Sun, Jennifer},
    citeulike-article-id = {8242108},
    citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1842733.1842736},
    citeulike-linkout-1 = {http://dx.doi.org/10.1145/1842733.1842736},
    doi = {10.1145/1842733.1842736},
    issn = {0163-5980},
    journal = {SIGOPS Oper. Syst. Rev.},
    keywords = {network},
    month = aug,
    number = {3},
    pages = {2--19},
    posted-at = {2011-08-21 08:52:11},
    priority = {2},
    publisher = {ACM},
    title = {{The Akamai network: a platform for high-performance internet applications}},
    url = {http://dx.doi.org/10.1145/1842733.1842736},
    volume = {44},
    year = {2010}
}

@inproceedings{Gupta-ProbLE-DISC,
 author = {Gupta, Indranil and Renesse, Robbert van and Birman, Kenneth P.},
 title = {A Probabilistically Correct Leader Election Protocol for Large Groups},
 booktitle = {Proceedings of the 14th International Conference on Distributed Computing},
 series = {DISC '00},
 year = {2000},
 isbn = {3-540-41143-7},
 pages = {89--103},
 numpages = {15},
 url = {http://dl.acm.org/citation.cfm?id=645957.675964},
 acmid = {675964},
 keywords = {asynchronous networks, fault-tolerance, leader election, process groups, randomized protocols, scalable protocols},
}

@ARTICLE{ KrishnaRamanathan:randomized,
AUTHOR = "Murali Krishna Ramanathan and Ronaldo A. Ferreira and Suresh Jagannathan and Ananth Grama and Wojciech Szpankowski",
TITLE = "Randomized leader election",
JOURNAL = "Distributed Computing",
PAGES = {403-418},
YEAR = {2007},
  }

@inproceedings{Lann77-DistSystems,
  author    = {G{\'e}rard Le Lann},
  title     = {Distributed Systems - Towards a Formal Approach},
  booktitle = {IFIP Congress},
  year      = {1977},
  pages     = {155-160},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{KorachKuttenMoran-ModularLE-TOPLAS,
 author = {Korach, E. and Kutten, S. and Moran, S.},
 title = {A modular technique for the design of efficient distributed leader finding algorithms},
 journal = {ACM Trans. Program. Lang. Syst.},
 issue_date = {Jan. 1990},
 volume = {12},
 number = {1},
 month = jan,
 year = {1990},
 issn = {0164-0925},
 pages = {84--101},
 numpages = {18},
 url = {http://doi.acm.org/10.1145/77606.77610},
 doi = {10.1145/77606.77610},
 acmid = {77610},
 publisher = {ACM},
 address = {New York, NY, USA},
}


@article{itai-rodeh,
 author = {Alon Itai and Michael Rodeh},
 title = {Symmetry breaking in distributed networks},
 journal = {Inf. Comput.},
 volume = {88},
 number = {1},
 year = {1990},
  pages = {60--87},
}


@article{afek-matias,
 author = {Yehuda Afek and Yossi Matias},
 title = {Elections in Anonymous Networks},
 journal = {Inf. Comput.},
 volume = {113},
 number = {2},
 year = {1994},
  pages = {312--330},
}

@article{snir-sbar,
 author = {Baruch Scheiber, Marc Snir},
 title = {Calling Names on Nameless Networks},
 journal = {Inf. Comput.},
 volume = {113},
 number = {1},
 year = {1994},
  pages = {80--101},
}



@inproceedings{KorachKuttenMoran-ModularLE-PODC,
 author = {Korach, E. and Kutten, S. and Moran, S.},
 title = {A modular technique for the design of efficient distributed leader finding algorithms},
 booktitle = {Proceedings of the fourth annual ACM symposium on Principles of distributed computing},
 series = {PODC '85},
 year = {1985},
 isbn = {0-89791-168-7},
 location = {Minaki, Ontario, Canada},
 pages = {163--174},
 numpages = {12},
 url = {http://doi.acm.org/10.1145/323596.323611},
 doi = {10.1145/323596.323611},
 acmid = {323611},
 publisher = {ACM},
 address = {New York, NY, USA},
}


@article{KorachOptimal89,
title = "Optimal lower bounds for some distributed algorithms for a complete network of processors",
journal = "Theoretical Computer Science",
volume = "64",
number = "1",
pages = "125 - 132",
year = "1989",
note = "",
issn = "0304-3975",
doi = "10.1016/0304-3975(89)90103-5",
url = "http://www.sciencedirect.com/science/article/pii/0304397589901035",
author = "E. Korach and S. Moran and S. Zaks"
}

@inproceedings{singh,
  author    = {G. Singh},
  title     = {Efficient distributed algorithms for leader election in
               complete networks},
  booktitle = {ICDCS},
  year      = {1991},
  pages     = {472-479},
  ee        = {http://dx.doi.org/10.1109/ICDCS.1991.148712},
  crossref  = {DBLP:conf/icdcs/1991},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@inproceedings{KorachPODC1984,
 author = {Korach, E. and Moran, S. and Zaks, S.},
 title = {Tight lower and upper bounds for some distributed algorithms for a complete network of processors},
 booktitle = {PODC 1984},
 year = {1984},
 isbn = {0-89791-143-1},
 location = {Vancouver, British Columbia, Canada},
 pages = {199--207},
 numpages = {9},
 url = {http://doi.acm.org/10.1145/800222.806747},
 doi = {10.1145/800222.806747},
 acmid = {806747},
 publisher = {ACM},
 address = {New York, NY, USA},
}

@article{KorachOptimalTrees87,
author = {Korach, E. and Moran, S. and Zaks, S.},
title = {The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors},
journal = {SIAM Journal on Computing},
volume = {16},
number = {2},
pages = {231-236},
year = {1987},
doi = {10.1137/0216019},

URL = {http://epubs.siam.org/doi/abs/10.1137/0216019},
eprint = {http://epubs.siam.org/doi/pdf/10.1137/0216019}
}



@inproceedings{Ratnasamy01CAN,
 author = {Ratnasamy, Sylvia and Francis, Paul and Handley, Mark and Karp, Richard and Shenker, Scott},
 title = {A scalable content-addressable network},
 booktitle = {SIGCOMM 2001},
 year = {2001},
 isbn = {1-58113-411-8},
 location = {San Diego, California, United States},
 pages = {161--172},
 numpages = {12},
 url = {http://doi.acm.org/10.1145/383059.383072},
 doi = {http://doi.acm.org/10.1145/383059.383072},
 acmid = {383072},
 publisher = {ACM},
 address = {New York, NY, USA},
}


@inproceedings{Rowstron01Pastry,
 author = {Rowstron, Antony I. T. and Druschel, Peter},
 title = {Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems},
 booktitle = {Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg},
 series = {Middleware '01},
 year = {2001},
 isbn = {3-540-42800-3},
 pages = {329--350},
 numpages = {22},
 url = {http://dl.acm.org/citation.cfm?id=646591.697650},
 acmid = {697650},
 publisher = {Springer-Verlag},
}


@ARTICLE{Zhao04Tapestry,
author={Zhao, B.Y. and Ling Huang and Stribling, J. and Rhea, S.C. and Joseph, A.D. and Kubiatowicz, J.D.},
journal={Selected Areas in Communications, IEEE Journal on},
title={Tapestry: a resilient global-scale overlay for service deployment},
year={2004},
month={jan.},
volume={22},
number={1},
pages={ 41 - 53},
keywords={ Internet; PlanetLab; Tapestry; applications programming interface; decentralized object location and routing; decentralized routing; localized resources; overlay networks; peer-to-peer overlay routing infrastructure; self-repairing routing layer; service deployment; soft-state-based routing layer; Internet; application program interfaces; telecommunication computing; telecommunication network routing; telecommunication services;},
doi={10.1109/JSAC.2003.818784},
ISSN={0733-8716},}


@inproceedings{Malkhi-ProbQSystems,
 author = {Malkhi, Dahlia and Reiter, Michael and Wright, Rebecca},
 title = {Probabilistic quorum systems},
 booktitle = {PODC 1997},
 year = {1997},
 isbn = {0-89791-952-1},
 location = {Santa Barbara, California, United States},
 pages = {267--273},
 numpages = {7},
 url = {http://doi.acm.org/10.1145/259380.259458},
 doi = {10.1145/259380.259458},
 acmid = {259458},
 publisher = {ACM},
 address = {New York, NY, USA},
}
@article{Maekawa:1985:MutEx,
 author = {Maekawa, Mamoru},
 title = {A   N  algorithm for mutual exclusion in decentralized systems},
 journal = {ACM Trans. Comput. Syst.},
 issue_date = {May 1985},
 volume = {3},
 number = {2},
 month = may,
 year = {1985},
 issn = {0734-2071},
 pages = {145--159},
 numpages = {15},
 url = {http://doi.acm.org/10.1145/214438.214445},
 doi = {10.1145/214438.214445},
 acmid = {214445},
 publisher = {ACM},
 address = {New York, NY, USA},
}


@inproceedings{AngluinSTOC80,
  author    = {Dana Angluin},
  title     = {Local and Global Properties in Networks of Processors (Extended
               Abstract)},
  booktitle = {STOC},
  year      = {1980},
  pages     = {82-93},
  ee        = {http://doi.acm.org/10.1145/800141.804655},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}





@inproceedings{dmitry,
  author    = {Dmitry Zinenko and Shay Kutten},
  title     = {Low Communication Self-Stabilization Through Randomization},
  booktitle = {DISC},
  year      = {2010},
 }


@article{motwani-raghavan,
 author = {Motwani, Rajeev and Raghavan, Prabhakar},
 title = {Randomized algorithms},
 journal = {ACM Comput. Surv.},
 issue_date = {March 1996},
 volume = {28},
 number = {1},
 month = mar,
 year = {1996},
 issn = {0360-0300},
 pages = {33--37},
 numpages = {5},
 url = {http://doi.acm.org/10.1145/234313.234327},
 doi = {10.1145/234313.234327},
 acmid = {234327},
 publisher = {ACM},
 address = {New York, NY, USA},
} 




@article{GallagerHS1983,
 author = {Gallager, R. G. and Humblet, P. A. and Spira, P. M.},
 title = {A Distributed Algorithm for Minimum-Weight Spanning Trees},
 journal = {ACM Trans. Program. Lang. Syst.},
 issue_date = {Jan. 1983},
 volume = {5},
 number = {1},
 month = jan,
 year = {1983},
 issn = {0164-0925},
 pages = {66--77},
 numpages = {12},
 url = {http://doi.acm.org/10.1145/357195.357200},
 doi = {10.1145/357195.357200},
 acmid = {357200},
 publisher = {ACM},
 address = {New York, NY, USA},
}

@inproceedings{Chandra-PaxosTalk-PODC07,
title = {Paxos Made Live - An Engineering Perspective (2006 Invited Talk)},
author  = {Tushar Deepak Chandra and Robert Griesemer and Joshua Redstone},
year  = 2007,
URL = {http://www.chandrakin.com/paper2.pdf},
booktitle = {Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing}
}

@article{Lamport-Paxos98,
 author = {Lamport, Leslie},
 title = {The part-time parliament},
 journal = {ACM Trans. Comput. Syst.},
 issue_date = {May 1998},
 volume = {16},
 number = {2},
 month = may,
 year = {1998},
 issn = {0734-2071},
 pages = {133--169},
 numpages = {37},
 url = {http://doi.acm.org/10.1145/279227.279229},
 doi = {10.1145/279227.279229},
 acmid = {279229},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {state machines, three-phase commit, voting},
}


@article{sense-of-dir,
 author = {Loui M. C. and Matsushita T. A. and West D. B.},
 title = {Election in a complete network with a sense of direction},
 journal = {Information Processing Letters},
 volume = {22},
 number = {4},
 year = {1986},
 pages = {185--187},
 }


@UnPublished{humblet-clique,
Author={Humblet,  P},
Title={Electing  a  leader  in  a  clique  in  {$O(n  \log  n)$}
messages},
Year ={1984},
Note={Intern.  Memo.,  Laboratory
 for  Information  and  Decision  Systems,  M.I.T.,  Cambridge,  Mass}
}

@article{peleg-jpdc,
title = "Time-optimal leader election in general networks",
journal = "Journal of Parallel and Distributed Computing",
volume = "8",
number = "1",
pages = "96 - 99",
year = "1990",
note = "",
issn = "0743-7315",
doi = "10.1016/0743-7315(90)90074-Y",
url = "http://www.sciencedirect.com/science/article/pii/074373159090074Y",
author = "David Peleg"
}

@book{santoro-book,
 author = {Santoro, Nicola},
 title = {Design and Analysis of Distributed Algorithms (Wiley Series on Parallel and Distributed Computing)},
 year = {2006},
 isbn = {0471719978},
 publisher = {Wiley-Interscience},
}

@book{GerardTelDistributedAlgosBook,
 author = {Tel, Gerard},
 title = {Introduction to distributed algorithms},
 year = {1994},
 isbn = {0-521-47096-2},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
 }

@COMMENT = {End copied from leaderelecrt.bib}


@article{BS2007:Simple,
  author    = {Surender Baswana and
               Sandeep Sen},
  title     = {A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs.},
  journal   = { Random Struct. Algorithms},
  volume    = {30},
  number    = {4},
  year      = {2007},
  pages     = {532-563},
}




@article{sensor,
 author = {Yao, Yong and Gehrke, Johannes},
 title = {The cougar approach to in-network query processing in sensor networks},
 journal = {SIGMOD Rec.},
 issue_date = {September 2002},
 volume = {31},
 number = {3},
 month = sep,
 year = {2002},
 issn = {0163-5808},
 pages = {9--18},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/601858.601861},
 doi = {10.1145/601858.601861},
 acmid = {601861},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@inproceedings{sensor2,
 author = {Ganeriwal, Saurabh and Kumar, Ram and Srivastava, Mani B.},
 title = {Timing-sync protocol for sensor networks},
 booktitle = {Proceedings of the 1st international conference on Embedded networked sensor systems},
 series = {SenSys '03},
 year = {2003},
 isbn = {1-58113-707-9},
 location = {Los Angeles, California, USA},
 pages = {138--149},
 numpages = {12},
 url = {http://doi.acm.org/10.1145/958491.958508},
 doi = {10.1145/958491.958508},
 acmid = {958508},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {clock drift, medium access control, packet delay, sensor networks, time synchronization},
} 



@inproceedings{awerbuch-mst,
 author = {Awerbuch, B.},
 title = {Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems},
 booktitle = {Proceedings of the nineteenth annual ACM symposium on Theory of computing},
 series = {STOC '87},
 year = {1987},
 isbn = {0-89791-221-7},
 location = {New York, New York, USA},
 pages = {230--240},
 numpages = {11},
 url = {http://doi.acm.org/10.1145/28395.28421},
 doi = {10.1145/28395.28421},
 acmid = {28421},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@article{peleg-Vainish,
 author = {Awerbuch, Baruch and Goldreich, Oded and Vainish, Ronen and Peleg, David},
 title = {A trade-off between information and communication in broadcast protocols},
 journal = {J. ACM},
 issue_date = {April 1990},
 volume = {37},
 number = {2},
 month = apr,
 year = {1990},
 issn = {0004-5411},
 pages = {238--256},
 numpages = {19},
 url = {http://doi.acm.org/10.1145/77600.77618},
 doi = {10.1145/77600.77618},
 acmid = {77618},
 publisher = {ACM},
 address = {New York, NY, USA},
} 



@inproceedings{KPPRT-LE-ICDCN13,
 author= {Shay Kutten and Gopal Pandurangan and David Peleg and Peter Robinson and Amitabh Trehan},
 title= {Sublinear Bounds for
Randomized Leader Election},
booktitle = "ICDCN'13",
pages="348-362",
 year={2013},
}


 
@inproceedings{AngluinSTOC80,
  author    = {Dana Angluin},
  title     = {Local and Global Properties in Networks of Processors (Extended
               Abstract)},
  booktitle = {STOC},
  year      = {1980},
  pages     = {82-93},
  ee        = {http://doi.acm.org/10.1145/800141.804655},
  crossref  = {DBLP:conf/stoc/STOC12},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@INPROCEEDINGS{Abu-amara,
author={Abu-Amara, H. and Kanevsky, A.},
booktitle={Proceedings of the Fifth International Conference on Computing and Information (ICCI)}, title={On the complexities of leader election algorithms},
year={1993},
month={may},
volume={},
number={},
pages={202 -206},
keywords={Algorithm design and analysis;Application software;Collaboration;Communication channels;Communication networks;Communication standards;Computer science;Distributed algorithms;Network topology;Nominations and elections;communication complexity;computational complexity;distributed algorithms;performance evaluation;complexities;general networks;leader election algorithms;message complexity;time distributed algorithm;},
doi={10.1109/ICCI.1993.315378},
ISSN={},}

@inproceedings{soda12,
 author = {John Augustine and Gopal Pandurangan and Peter Robinson and Eli Upfal},
 title = {Towards Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks},
 booktitle = {SODA},
 year = {2012}}


@book{AW04,
  author = {Hagit Attiya and Jennifer Welch},
  title = {Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition)},
  publisher = {John Wiley Interscience},
  year = {2004},
  month = {March},
  isbn = {0-471-453242}
}

@article{DemboZ98,
author = {A. Dembo and O. Zeitouni},
title = {Large deviations techniques and applications},
journal = {Elearn},
year = {1998},
masid = {1927814}
}

@book{grinstead1997introduction,
  title={Introduction to probability},
  author={Grinstead, C.M. and Snell, J.L.},
  isbn={9780821807491},
  lccn={97008126},
  url={http://books.google.com/books?id=14oq4uWGCkwC},
  year={1997},
  publisher={American Mathematical Society}
}



@article{KhanKMPT08,
  author    = {Maleq Khan and
               Fabian Kuhn and
               Dahlia Malkhi and
               Gopal Pandurangan and
               Kunal Talwar},
  title     = {Efficient distributed approximation algorithms via probabilistic
               tree embeddings},
  journal   = {Distributed Computing},
  volume    = {25},
  number    = {3},
  year      = {2012},
  pages     = {189-205},
  ee        = {http://dx.doi.org/10.1007/s00446-012-0157-9},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}



@article{AoyamaS08,
  author    = {Damon Mosk-Aoyama and
               Devavrat Shah},
  title     = {Fast Distributed Algorithms for Computing Separable Functions},
  journal   = {IEEE Transactions on Information Theory},
  volume    = {54},
  number    = {7},
  year      = {2008},
  pages     = {2997-3007},
  ee        = {http://dx.doi.org/10.1109/TIT.2008.924648},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@Book{Pel00,
  author = "David Peleg",
  title = "Distributed Computing: A Locality-Sensitive Approach",
  publisher = "SIAM",
  address = "Philadelphia",
  year = "2000",
  isbn = "0-89871-464-8"
}


@ARTICLE{FLP85,
  author =	 "Michael J. Fischer and Nancy A. Lynch and
                  M. S. Paterson",
  title =	 "Impossibility of Distributed Consensus with one
                  Faulty Process",
  journal =	 "Journal of the ACM",
  volume =	 32,
  number =	 2,
  year =	 1985,
  month =	 apr,
  pages =	 "374--382"
}

@ARTICLE{FLynch,
    author = "Greg N. Frederickson and Nancy A. Lynch",
    title  = "Electing a leader in a synchronous ring",
    journal= "Journal of the ACM",
    volume =  34,
    number =  1,
    year   =  1987,
    pages  =  "98--115"
    }


@Article{AT98,
  author    = {Marcos Kawazoe Aguilera and
               Sam Toueg},
  title     = {A Simple Bivalency Proof that t-Resilient Consensus
               Requires t+1 Rounds},
  journal   = {Inf. Process. Lett.},
  volume    = {71},
  number    = {3--4},
  year      = {1999},
  pages     = {155--158},
  ee        = {http://dx.doi.org/10.1016/S0020-0190(99)00100-3},
}

@inproceedings{KSSV06,
  author    = {Valerie King and
               Jared Saia and
               Vishal Sanwalani and
               Erik Vee},
  title     = {Towards Secure and Scalable Computation in Peer-to-Peer
               Networks},
  booktitle = {FOCS},
  year      = {2006},
  pages     = {87-98},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.77},
}

@inproceedings{KOM11,
 author = {Kuhn, Fabian and Oshman, Rotem and Moses, Yoram},
 title = {Coordinated consensus in dynamic networks},
 booktitle = {Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing},
 series = {PODC '11},
 year = {2011},
 isbn = {978-1-4503-0719-2},
 location = {San Jose, California, USA},
 pages = {1--10},
 numpages = {10},
 acmid = {1993808},
 publisher = {ACM},
}

@article{Upfal94,
  author    = {Eli Upfal},
  title     = {Tolerating a Linear Number of Faults in Networks of Bounded
               Degree},
  journal   = {Inf. Comput.},
  volume    = {115},
  number    = {2},
  year      = {1994},
  pages     = {312-320},
  ee        = {http://dx.doi.org/10.1006/inco.1994.1099},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{DPPU88,
  author    = {Cynthia Dwork and
               David Peleg and
               Nicholas Pippenger and
               Eli Upfal},
  title     = {Fault Tolerance in Networks of Bounded Degree},
  journal   = {SIAM J. Comput.},
  volume    = {17},
  number    = {5},
  year      = {1988},
  pages     = {975-988},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{CH:PODC10,
 author = {Censor Hillel, Keren and Shachnai, Hadas},
 title = {Partial information spreading with application to distributed maximum coverage},
 booktitle = {Proceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing},
 series = {PODC '10},
 year = {2010},
 isbn = {978-1-60558-888-9},
 location = {Zurich, Switzerland},
 pages = {161--170},
 numpages = {10},
 url = {http://doi.acm.org.ezlibproxy1.ntu.edu.sg/10.1145/1835698.1835739},
 doi = {http://doi.acm.org.ezlibproxy1.ntu.edu.sg/10.1145/1835698.1835739},
 acmid = {1835739},
 publisher = {ACM},
}

@inproceedings{ARS07,
  author    = {James Aspnes and
               Navin Rustagi and
               Jared Saia},
  title     = {Worm Versus Alert: Who Wins in a Battle for Control of a
               Large-Scale Network?},
  booktitle = {OPODIS},
  year      = {2007},
  pages     = {443-456},
  crossref  = {DBLP:conf/opodis/2007},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{BBCES2006,
  author    = {Amitabha Bagchi and
               Ankur Bhargava and
               Amitabh Chaudhary and
               David Eppstein and
               Christian Scheideler},
  title     = {The Effect of Faults on Network Expansion},
  journal   = {Theory Comput. Syst.},
  volume    = {39},
  number    = {6},
  year      = {2006},
  pages     = {903-928},
  ee        = {http://dx.doi.org/10.1007/s00224-006-1349-0},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Cohen97,
  author    = {Edith Cohen},
  title     = {Size-Estimation Framework with Applications to Transitive
               Closure and Reachability},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {55},
  number    = {3},
  year      = {1997},
  pages     = {441-453},
  ee        = {http://dx.doi.org/10.1006/jcss.1997.1534},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{MAS08,
  author    = {Damon Mosk-Aoyama and
               Devavrat Shah},
  title     = {Fast Distributed Algorithms for Computing Separable Functions},
  journal   = {IEEE Transactions on Information Theory},
  volume    = {54},
  number    = {7},
  year      = {2008},
  pages     = {2997-3007},
  ee        = {http://dx.doi.org/10.1109/TIT.2008.924648},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS{LS03,
author={Law, C. and Siu, K.-Y.},
booktitle={INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies}, title={Distributed construction of random expander networks},
year={2003},
month={march-3 april},
volume={3},
number={},
pages={ 2133 - 2143 vol.3},
}

@inproceedings{DGMSS11,
  author    = {Benjamin Doerr and
               Leslie Ann Goldberg and
               Lorenz Minder and
               Thomas Sauerwald and
               Christian Scheideler},
  title     = {Stabilizing consensus with the power of two choices},
  booktitle = {SPAA},
  year      = {2011},
  pages     = {149-158},
}



@article{KS10,
 author = {King, Valerie and Saia, Jared},
 title = {Breaking the {$O(n^2)$} bit barrier: Scalable byzantine agreement with an adaptive adversary},
 journal = {J. ACM},
 issue_date = {July 2011},
 volume = {58},
 issue = {4},
 month = {July},
 year = {2011},
 issn = {0004-5411},
 pages = {18:1--18:24},
 articleno = {18},
 numpages = {24},
 publisher = {ACM},
}


@inproceedings{KSS06,
  author    = {Valerie King and
               Jared Saia and
               Vishal Sanwalani and
               Erik Vee},
  title     = {Scalable leader election},
  booktitle = {SODA},
  year      = {2006},
  pages     = {990-999},
}

@article{KKKSS10,
  author    = {Bruce M. Kapron and
               David Kempe and
               Valerie King and
               Jared Saia and
               Vishal Sanwalani},
  title     = {Fast asynchronous Byzantine agreement and leader election
               with full information},
  journal   = {ACM Transactions on Algorithms},
  volume    = {6},
  number    = {4},
  year      = {2010},
}

@Book{Lyn96,
  author =	 {Nancy Lynch},
  title =	 {Distributed Algorithms},
  publisher =	 {Morgan Kaufman Publishers, Inc.},
  address =      {San Francisco, USA},
  year =	 {1996},
}

@article{Dolev82,
  author    = {Danny Dolev},
  title     = {The Byzantine Generals Strike Again},
  journal   = {J. Algorithms},
  volume    = {3},
  number    = {1},
  year      = {1982},
  pages     = {14-30},
}

@article{PSL80,
  author    = {Marshall C. Pease and
               Robert E. Shostak and
               Leslie Lamport},
  title     = {Reaching Agreement in the Presence of Faults},
  journal   = {J. ACM},
  volume    = {27},
  number    = {2},
  year      = {1980},
  pages     = {228-234},
}


@article{KKM,
  author    = {Ephraim Korach and Shay Kutten and Shlomo Moran},
  title     = {A Modular Technique for the Design of Efficient
Distributed Leader Finding Algorithms},
  journal   = {ACM Trans. Program. Lang. Syst},
  volume    = {12},
  number    = {1},
  year      = {1990},
  pages     = {84-101},
}


 



@misc{Cloudmark,
  author  = {Cloudmark Inc., Website of},
  title = {http://cloudmark.com/}
}

@article{SGG02,
  author    = {P. Krishna Gummadi and
               Stefan Saroiu and
               Steven D. Gribble},
  title     = {A measurement study of Napster and Gnutella as examples
               of peer-to-peer file sharing systems},
  journal   = {Computer Communication Review},
  volume    = {32},
  number    = {1},
  year      = {2002},
  pages     = {82},
}
``
@inproceedings{SW02,
 author = {Sen, Subhabrata and Wang, Jia},
 title = {Analyzing peer-to-peer traffic across large networks},
 booktitle = {Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment},
 series = {IMW '02},
 year = {2002},
 isbn = {1-58113-603-X},
 location = {Marseille, France},
 pages = {137--150},
 numpages = {14},
 publisher = {ACM},
 address = {New York, NY, USA},
}

@inproceedings{SR06,
 author = {Stutzbach, Daniel and Rejaie, Reza},
 title = {Understanding churn in peer-to-peer networks},
 booktitle = {Proceedings of the 6th ACM SIGCOMM conference on Internet measurement},
 series = {IMC '06},
 year = {2006},
 isbn = {1-59593-561-4},
 location = {Rio de Janeriro, Brazil},
 pages = {189--202},
 numpages = {14},
 publisher = {ACM},
 address = {New York, NY, USA},
}

@article{BG93,
  author    = {Piotr Berman and
               Juan A. Garay},
  title     = {Fast Consensus in Networks of Bounded Degree},
  journal   = {Distributed Computing},
  volume    = {7},
  number    = {2},
  year      = {1993},
  pages     = {67-73},
}

@inproceedings{Canny02,
  author    = {John F. Canny},
  title     = {Collaborative Filtering with Privacy},
  booktitle = {IEEE Symposium on Security and Privacy},
  year      = {2002},
  pages     = {45-57},
}

@article{DBGWK06,
  author    = {Souptik Datta and
               Kanishka Bhaduri and
               Chris Giannella and
               Ran Wolff and
               Hillol Kargupta},
  title     = {Distributed Data Mining in Peer-to-Peer Networks},
  journal   = {IEEE Internet Computing},
  volume    = {10},
  number    = {4},
  year      = {2006},
  pages     = {18-26},
}


@article{VAS04,
 author = {Vlachos, Vasileios and Androutsellis-Theotokis, Stephanos and Spinellis, Diomidis},
 title = {Security applications of peer-to-peer networks},
 journal = {Comput. Netw.},
 volume = {45},
 issue = {2},
 month = {June},
 year = {2004},
 issn = {1389-1286},
 pages = {195--205},
 numpages = {11},
 publisher = {Elsevier North-Holland, Inc.},
 address = {New York, NY, USA},
}

@inproceedings{MS05,
  author = {David J. Malan and Michael D. Smith},
  booktitle = {WORM},
  editor = {Vijay Atluri and Angelos D. Keromytis},
  pages = {72-80},
  publisher = {ACM Press},
  title = {Host-based detection of worms through peer-to-peer cooperation.},
  year = 2005,
}

@inproceedings{PRU01,
  author    = {Gopal Pandurangan and
               Prabhakar Raghavan and
               Eli Upfal},
  title     = {Building Low-Diameter {P2P} Networks},
  booktitle = {FOCS},
  year      = {2001},
  pages     = {492-499},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article {AS09,
   author = {Awerbuch, Baruch and Scheideler, Christian},
   title = {Towards a Scalable and Robust {DHT}},
   journal = {Theory of Computing Systems},
   publisher = {Springer New York},
   issn = {1432-4350},
   keyword = {Computer Science},
   pages = {234-260},
   volume = {45},
   issue = {2},
   year = {2009}
}

@inproceedings{FS02,
  author    = {Amos Fiat and
               Jared Saia},
  title     = {Censorship resistant peer-to-peer content addressable networks},
  booktitle = {SODA},
  year      = {2002},
  pages     = {94-103},
}
@inproceedings{NW03,
  author    = {Moni Naor and
               Udi Wieder},
  title     = {A Simple Fault Tolerant Distributed Hash Table},
  booktitle = {IPTPS},
  year      = {2003},
  pages     = {88-97},
}
@inproceedings{HK03,
  author = {Kirsten Hildrum and John Kubiatowicz},
  booktitle = {DISC},
  pages = {321-336},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  title = {Asymptotically Efficient Approaches to Fault-Tolerance in Peer-to-Peer Networks.},
  volume = 2848,
  year = 2003,
}
@inproceedings{Scheideler05,
  author    = {Christian Scheideler},
  title     = {How to spread adversarial nodes?: rotate!},
  booktitle = {STOC},
  year      = {2005},
  pages     = {704-713},
  ee        = {http://doi.acm.org/10.1145/1060590.1060694},
}
@inproceedings{BCF09,
  author    = {Herv{\'e} Baumann and
               Pierluigi Crescenzi and
               Pierre Fraigniaud},
  title     = {Parsimonious flooding in dynamic graphs},
  booktitle = {PODC},
  year      = {2009},
  pages     = {260-269},
}

@inproceedings{FPJKA07,
  author    = {Jarret Falkner and
               Michael Piatek and
               John P. John and
               Arvind Krishnamurthy and
               Thomas E. Anderson},
  title     = {Profiling a million user dht},
  booktitle = {Internet Measurement Comference},
  year      = {2007},
  pages     = {129-134},
  ee        = {http://doi.acm.org/10.1145/1298306.1298325},
}

@inproceedings{GKLL09,
  author    = {Roxana Geambasu and
               Tadayoshi Kohno and
               Amit A. Levy and
               Henry M. Levy},
  title     = {Vanish: Increasing Data Privacy with Self-Destructing Data},
  booktitle = {USENIX Security Symposium},
  year      = {2009},
  pages     = {299-316},
}

@inproceedings{PT11,
  author    = {Gopal Pandurangan and
               Amitabh Trehan},
  title     = {Xheal: localized self-healing using expanders},
  booktitle = {PODC},
  year      = {2011},
  pages     = {301-310},
  ee        = {http://doi.acm.org/10.1145/1993806.1993865},
  crossref  = {DBLP:conf/podc/2011},
}

@inproceedings{FSY05,
  author    = {Amos Fiat and
               Jared Saia and
               Maxwell Young},
  title     = {Making Chord Robust to Byzantine Attacks},
  booktitle = {ESA},
  year      = {2005},
  pages     = {803-814},
}

@inproceedings{Hae11,
  author    = {Bernhard Haeupler},
  title     = {Analyzing network coding gossip made easy},
  booktitle = {STOC},
  year      = {2011},
  pages     = {293-302},
  ee        = {http://doi.acm.org/10.1145/1993636.1993676},
}

@inproceedings{OW05,
  author    = {Regina O'Dell and
               Roger Wattenhofer},
  title     = {Information dissemination in highly dynamic graphs},
  booktitle = {DIALM-POMC},
  year      = {2005},
  pages     = {104-110},
  ee        = {http://doi.acm.org/10.1145/1080810.1080828},
}

@article{KSW10,
  author    = {Fabian Kuhn and
               Stefan Schmid and
               Roger Wattenhofer},
  title     = {Towards worst-case churn resistant peer-to-peer systems},
  journal   = {Distributed Computing},
  volume    = {22},
  number    = {4},
  year      = {2010},
  pages     = {249-267},
}


@incollection {SS09,
   author = {Scheideler, Christian and Schmid, Stefan},
   affiliation = {Technische Universität München Institut für Informatik D-85748 Garching Germany},
   title = {A Distributed and Oblivious Heap},
   booktitle = {Automata, Languages and Programming},
   series = {Lecture Notes in Computer Science},
   publisher = {Springer Berlin / Heidelberg},
   keyword = {Computer Science},
   pages = {571-582},
   volume = {5556},
   year = {2009}
}


@inproceedings{CRW11,
 author = {Chung, Hyun Chul and Robinson, Peter and Welch, Jennifer L.},
 title = {Optimal regional consecutive leader election in mobile ad-hoc networks},
 booktitle = {Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing},
 series = {FOMC '11},
 year = {2011},
 isbn = {978-1-4503-0779-6},
 location = {San Jose, California},
 pages = {52--61},
 numpages = {10},
  ee        = {http://dx.doi.org/10.1007/s00446-010-0099-z},
 doi = {http://doi.acm.org/10.1145/1998476.1998485},
 acmid = {1998485},
 publisher = {ACM},
}


@inproceedings{avin1,
author = {Chen Avin and Michael Borokhovich and Keren Censor-Hillel and Zvi Lotker},
title = {Order Optimal Information Spreading Using Algebraic Gossip},
booktitle = {ACM  PODC},
year = {2011},
pages = {363-372}
}


@inproceedings{avin2,
author = {Michael Borokhovich and Chen Avin and Zvi Lotker},
title = {Tight Bounds for Algebraic Gossip on Graphs},
booktitle = {IEEE ISIT},
year = {2010}
}


@article{kuhn-survey,
author = {F. Kuhn and R. Oshman},
title = {Dynamic networks: Models and algorithms},
journal ={SIGACT News},
volume = {42(1)},
pages = {82-96},
 year = {2011}
}

@inproceedings{kuhn+lo:dynamic,
 author = {Kuhn, Fabian and Lynch, Nancy and Oshman, Rotem},
 title = {Distributed computation in dynamic networks},
 booktitle = {ACM STOC},
 year = {2010},
 pages = {513--522},
}

@article{chernoff,
  title = {Asymptotic efficiency for tests based on the sum of observations},
  author = {H. Chernoff},
  journal = {Math. Stat.},
  year = {1952},
}

@article{hoeffding,
  title = {Probability for sums of bounded random variables},
  author = {W. Hoeffding},
  journal = {Journal of American Statistical Association},
  year = {1963},
}

@article{angluin,
  title = {Fast probabilistic algorithms for Hamiltonian circuits and matchings},
  author = {D. Angluin and L.G. Valiant},
  journal = {Journal of Computer and System Sciences},
  year = {1979},
}

@book{upfal,
  title = {Probability and Computing: Randomized Algorithms and Probabilistic Analysis},
  author = {M. Mitzenmacher and E. Upfal},
  publisher = {Cambridge University Press},
  year = {2004},
}

@article{jain+ms:steiner,
  title = {Packing Steiner trees},
  author = {K. Jain and M. Mahdian and M. Salavatipour},
  journal = {SODA},
  year = {2003},
}

@article{cheriyan+s:steiner,
  title = {Hardness and Approximation Results for Packing Steiner Trees},
  author = {J. Cheriyan and M. Salavatipour},
  journal = {Algorithmica},
  year = {2006},
}

@article{charikar+ccdgg:steiner,
  title = {Approximation Algorithms for Directed Steiner Problems},
  author = {M. Charikar and C. Chekuri and T. Cheung and Z. Dai and A. Goel and S. Guha},
  journal = {Journal of Algorithms},
  year = {1998},
}

@article{lau:steiner,
  title = {An approximate max-steiner-tree-packing min-steiner-cut theorem},
  author = {L.C. Lau},
  journal = {FOCS},
  year = {2004},
}

@article{guruswami+krsy,
  title = {Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems},
  author = {V. Guruswami and S. Khanna and R. Rajaraman and B. Shepherd and M. Yannakakis},
  journal = {STOC},
  year = {1999},
}

@inproceedings{haeupler:gossip,
 author = {Haeupler, Bernhard},
 title = {Analyzing network coding gossip made easy},
 booktitle = {ACM STOC},
 year = {2011},
 pages = {293--302},
}

@inproceedings{haeupler+k:dynamic,
 author = {Haeupler, Bernhard and Karger, David},
 title = {Faster information dissemination in dynamic networks via network coding},
 booktitle = {ACM PODC},
 year = {2011},
 pages = {381--390},
}

@article{gafni:dynamic,
  title = {End-to-end communication in unreliable networks},
  author = {E. Gafni and Y. Afek},
  journal = {PODC},
  year = {1988}
}

@INPROCEEDINGS{afek+gr:slide,
    author = {Yehuda Afek and Eli Gafni and Adi Rosen},
    title = {The Slide Mechanism with Applications in Dynamic Networks},
    booktitle = {ACM PODC},
    year = {1992},
    pages = {35--46}
}

@article{awerbuch:adversarial,
  title = {Simple Routing Strategies for Adversarial Systems},
  author = {B. Awerbuch and P. Berenbrink and A. Brinkmann and C. Scheideler},
  journal = {FOCS},
  year = {2002}
}

@article{awerbuch:icalp,
  title = {Anycasting in adversarial systems: Routing and admission control},
  author = {B. Awerbuch and A. Brinkmann and C. Scheideler},
  journal = {ICALP},
  year = {2003}
}

@book{leighton:book,
author = "Leighton, F. T.",
title = "Introduction to Parallel Algorithms and Architectures: Arrays,
Trees, and Hypercubes",
publisher = "Morgan-Kaufmann",
year = "1991",
address = "San Mateo, CA",
}

@article{topkis:disseminate,
 author = {Topkis, Donald M.},
 title = {Concurrent Broadcast for Information Dissemination},
 journal = {IEEE Trans. Softw. Eng.},
 volume = {11},
 issue = {10},
 month = {October},
 year = {1985},
 pages = {1107--1112},
}


@book{dolev:stabilize,
 author = {Dolev, Shlomi},
 title = {Self-stabilization},
 year = {2000},
 publisher = {MIT Press},
 address = {Cambridge, MA, USA},
}

@article{gafni+b:link-reversal,
author = "Gafni, E. and Bertsekas, B.",
title = "Distributed algorithms for generating loop-free routes in networks with
frequently changing topology",
journal = "IEEE Trans. Comm.",
volume = "29",
number = "1",
pages = "11–18",
year = "1981",
}

@INPROCEEDINGS{afek+ag:dynamic,
AUTHOR = "Yehuda Afek and Baruch Awerbuch and Eli Gafni",
TITLE = "Applying Static Network Protocols to Dynamic Networks",
booktitle = "FOCS'87",
PAGES = {358-370},
YEAR = {1987},
}

@INPROCEEDINGS{awerbuch+pps:dynamic,
AUTHOR = "Baruch Awerbuch and Boaz Patt-Shamir and David Peleg and Michael E. Saks",
TITLE = "Adapting to Asynchronous Dynamic Networks",
booktitle = "STOC'92",
PAGES = {557-570},
YEAR = {1992}  }

@inproceedings{awerbuch+l:flow,
author = "Awerbuch, B. and Leighton, F. T.",
title = "Improved Approximation Algorithms for the Multi-commodity
Flow Problem and Local Competitive Routing in Dynamic Networks",
booktitle = "ACM STOC",
year = "1994",
month = "May",
pages = "487--496",
}

@inproceedings{awerbuch+bbs:route,
author = "Awerbuch, B. and Berenbrink, P. and Brinkmann, A. and Scheideler, C.",
title = "Simple Routing Strategies for Adversarial Systems",
booktitle = "IEEE FOCS",
year = "2001",
pages = "158--167",
}

@inproceedings{jia+rs:adhoc,
author = "Jia, L. and Rajaraman, R. and Scheideler, C.",
title = "On Local Algorithms for Topology Control and Routing in Ad Hoc Networks",
booktitle = "ACM SPAA",
year = "2003",
month = "June",
pages = "220--229",
}

@INPROCEEDINGS{awerbuch+bs:anycast,
AUTHOR = "Baruch Awerbuch and André Brinkmann and Christian Scheideler",
TITLE = "Anycasting in Adversarial Systems: Routing and Admission Control.",
booktitle = "ICALP'03",
PAGES = {1153-1168},
YEAR = {2003}  }

@article{alon+blp:radio,
author = "Alon, N. and Bar-Noy, A. and Linial, N. and Peleg, D.",
title = "A Lower Bound for Radio Broadcast",
journal = "Journal of Computer and System Sciences",
volume = "43",
year = "1991",
pages = "290--298",
}

@INPROCEEDINGS{clementi+ms:radio,
AUTHOR = "Andrea E. F. Clementi and Angelo Monti and Riccardo Silvestri",
TITLE = "Distributed multi-broadcast in unknown radio networks.",
booktitle = "PODC'01",
PAGES = {255-264},
YEAR = {2001}  }

@inproceedings{bar-yehuda+gi:radio,
 author = {Bar-Yehuda, R. and Goldreich, O. and Itai, A.},
 title = {On the time-complexity of broadcast in radio networks: an exponential gap between determinism and randomization},
 booktitle = {ACM PODC},
 year = {1987},
 pages = {98--108},
}

@article{ahlswede+cly:coding,
author = "Ahlswede, R. and Cai, N. and Li, S. and Yeung, R.",
title = "Network information flow",
journal = "Transactions on Information Theory",
volume = "46",
number = "4",
pages = "1204--1216",
year = "2000",
}

@inproceedings{zosin+k:steiner,
author = "Zosin, L. and Khuller, S.",
title = "On Directed {Steiner} Trees",
booktitle = "Proceedings of the 13th Annual ACM-SIAM Symposium on
Discrete Algorithms",
year = "2002",
month = "January",
}

@INPROCEEDINGS{sanders+et:flow,
    author = {Peter Sanders and Sebastian Egner and Ludo Tolhuizen},
    title = {Polynomial Time Algorithms for Network Information Flow},
    booktitle = {ACM SPAA},
    year = {2003},
    pages = {286--294}
}

@inproceedings{kempe1,
author = {D. Kempe and J. Kleinberg},
title ={Protocols and Impossibility Results for Gossip-Based Communication Mechanisms},
booktitle = {IEEE FOCS},
year = {2002}
}

@inproceedings{chen-spaa,
  author    = {J. Chen and G. Pandurangan},
  title     = {Optimal Gossip-based Aggregate Computation},
  booktitle = {SPAA},
  year      = {2010},
  pages     = {124-133}
}

@inproceedings{demers,
 author = {Alan Demers and Dan Greene and Carl Hauser and Wes Irish and John Larson and Scott Shenker and Howard Sturgis and Dan Swinehart and Doug Terry},
 title = {Epidemic algorithms for replicated database maintenance},
 booktitle = {PODC},
 year = {1987},
 pages = {1--12},
 }

@inproceedings{shah,
 author = {Damon Mosk-Aoyama and Devavrat Shah},
 title = {Computing separable functions via gossip},
 booktitle = {PODC},
 year = {2006},
 pages = {113--122}
 }

@inproceedings{karp,
 author = {R. M. Karp and C. Schindelhauer and S. Shenker and B. V\"{o}cking},
 title = {Randomized rumor spreading},
 booktitle = {FOCS},
 year = {2000},
 isbn = {0-7695-0850-2},
 pages = {565--574},
}

@inproceedings{kempe,
author ={D. Kempe and A. Dobra and J. Gehrke},
title={Gossip-based Computation of
Aggregate Information},
booktitle={FOCS},
year={2003},
pages={482--491},
}

@article{boyd,
 author = {S. Boyd and A. Ghosh and B. Prabhakar and D. Shah},
 title = {Randomized gossip algorithms},
 journal = {IEEE Trans. on Infor. Theory},
 volume = {52},
 number = {6},
 year = {2006},
 pages = {2508--2530}
  }

@INPROCEEDINGS{berenbrink+ceg:gossip,
AUTHOR = "Petra Berenbrink and Jurek Czyzowicz and Robert Els{\"{a}}sser and Leszek Gasieniec",
TITLE = "Efficient Information Exchange in the Random Phone-Call Model",
booktitle = "ICALP",
PAGES = {127-138},
YEAR = {2010}  }

@ARTICLE{bar-noy+gns:multicast,
AUTHOR = "Amotz Bar-Noy and Sudipto Guha and Joseph Naor and Baruch Schieber",
TITLE = "Message Multicasting in Heterogeneous Networks.",
JOURNAL = "SIAM J. Comput.",
PAGES = {347-358},
YEAR = {2000}  }

@inproceedings{avin+kl:dynamic,
 author = {Avin, Chen and Kouck\'{y}, Michal and Lotker, Zvi},
 title = {How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)},
 booktitle = {ICALP},
 year = {2008},
 pages = {121--132},
}

@inproceedings{agarwal+c:coding,
title = "On the advantage of Network Coding for Improving Network Throughput",
author = "Agarwal, A. and Charikar, M.",
booktitle = "Information Theory Workshop",
year = "2004",
}

@article{deb+mc:coding,
 author = {Deb, S. and M\'{e}dard, M. and Choute, C.},
 title = {Algebraic gossip: a network coding approach to optimal multiple rumor mongering},
 journal = {IEEE/ACM Trans. Netw.},
 volume = {14},
 month = {June},
 year = {2006},
 pages = {2486--2507},
}

@misc{crashplan,
  author  = {Crashplan Inc., Website of},
  title = {http://www.crashplan.com/}
}

@misc{wuala,
  author  = {Wuala Inc., Website of},
  title = {http://wuala.com/}
}

@misc{symform,
  author  = {Symform:, Website of},
  title = {http://www.symform.com/},
}

@article{p2p-storage-survey,
author ={Arjan Peddemors},
title ={Cloud Storage and Peer-to-Peer Storage - End-user considerations and product overview},
journal ={http://www.novay.nl/okb/publications/152},
year ={2010}
}




@inproceedings{SNP09:PODC,
  author    = {Atish Das Sarma and
               Danupon Nanongkai and
               Gopal Pandurangan},
  title     = {Fast distributed random walks},
  booktitle = {PODC},
  year      = {2009},
  pages     = {161-170},
  ee        = {http://doi.acm.org/10.1145/1582716.1582745},
  crossref  = {DBLP:conf/podc/2009},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@proceedings{DBLP:conf/podc/2009,
  editor    = {Srikanta Tirthapura and
               Lorenzo Alvisi},
  title     = {Proceedings of the 28th Annual ACM Symposium on Principles
               of Distributed Computing, PODC 2009, Calgary, Alberta, Canada,
               August 10-12, 2009},
  booktitle = {PODC},
  publisher = {ACM},
  year      = {2009},
  isbn      = {978-1-60558-396-9},
  ee        = {http://dl.acm.org/citation.cfm?id=1582716},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}






@article{AG1991:SICOMP,
author = {Afek, Y. and Gafni, E.},
title = {Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks},
journal = {SIAM Journal on Computing},
volume = {20},
number = {2},
pages = {376-394},
year = {1991},
doi = {10.1137/0220023},

URL = {http://epubs.siam.org/doi/abs/10.1137/0220023},
eprint = {http://epubs.siam.org/doi/pdf/10.1137/0220023}
}

@Article{Lam78,
 author = {Leslie Lamport},
 title = {Time, clocks, and the ordering of events in a distributed system},
 journal = {Commun. ACM},
 volume = {21},
 number = {7},
 year = {1978},
 issn = {0001-0782},
 pages = {558--565},
 doi = {http://doi.acm.org/10.1145/359545.359563},
 publisher = {ACM Press},
 OPTaddress = {New York, NY, USA},
}

@article{EKR1961:Intersection,
author = {Erd{\"o}s, P. and Ko, Chao and Rado, R.},
title = {Intersection theorems for systems of finite sets},
volume = {12},
number = {1},
pages = {313-320},
year = {1961},
doi = {10.1093/qmath/12.1.313},
URL = {http://qjmath.oxfordjournals.org/content/12/1/313.short},
eprint = {http://qjmath.oxfordjournals.org/content/12/1/313.full.pdf+html},
journal = {The Quarterly Journal of Mathematics}
}
@BOOK{MR1995:Randomized,
  title = {Randomized Algorithms},
  publisher = {Cambridge University Press},
  year = {1995},
  author = {Rajeev Motwani and Prabhakar Raghavan},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  isbn = {0-521-47465-5}
}

@inproceedings{AGPV88,
  author    = {Baruch Awerbuch and
               Oded Goldreich and
               David Peleg and
               Ronen Vainish},
  title     = {A Tradeoff between Information and Communication in Broadcast
               Protocols},
  booktitle = {AWOC},
  year      = {1988},
  pages     = {369-379},
  ee        = {http://dx.doi.org/10.1007/BFb0040404},
  crossref  = {DBLP:conf/awoc/1988},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{FP2012:ESA,
  author    = {Emanuele G. Fusco and
               Andrzej Pelc},
  title     = {Knowledge, Level of Symmetry, and Time of Leader Election},
  booktitle = {ESA},
  year      = {2012},
  pages     = {479-490}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 some refs: added by shay for the intro

@article{cole-vishkin,
  author    = {Richard Cole and
               Uzi Vishkin},
  title     = {Deterministic Coin Tossing with Applications to Optimal
               Parallel List Ranking},
  journal   = {Information and Control},
  volume    = {70},
  number    = {1},
  year      = {1986},
  pages     = {32-53},
  ee        = {http://dx.doi.org/10.1016/S0019-9958(86)80023-7},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
 
% \bibitem{cole-vishkin}
%Richard Cole and Uzi Vishkin.
%\newblock
%Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. %Information and Control 70(1): 32-53 (1986).

@book{elkin-book,
  author    = {Leonid Barenboim and
               Michael Elkin},
  title     = {Distributed Graph Coloring: Fundamentals and Recent Developments},
  booktitle = {Distributed Graph Coloring: Fundamentals and Recent Developments},
  publisher = {Morgan {\&} Claypool Publishers},
  series    = {Synthesis Lectures on Distributed Computing Theory},
  year      = {2013},
  isbn      = {9781627050180, 9781627050197},
  pages     = {1-171},
  ee        = {http://dx.doi.org/10.2200/S00520ED1V01Y201307DCT011},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
                                                                                          

%\bibitem{elkin-book}
%Leonid Barenboim and Michael Elkin.
% \newblock Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis %Lectures on Distributed Computing Theory, Morgan & Claypool Publishers 2013, ISBN %9781627050180, pp. 1-171.

@article{DBLP:journals/siamcomp/GarayKP98,
  author    = {Juan A. Garay and
               Shay Kutten and
               David Peleg},
  title     = {A Sublinear Time Distributed Algorithm for Minimum-Weight
               Spanning Trees},
  journal   = {SIAM J. Comput.},
  volume    = {27},
  number    = {1},
  year      = {1998},
  pages     = {302-316},
  ee        = {http://dx.doi.org/10.1137/S0097539794261118},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

%\bibitem{GarayKuttenPeleg} Juan A. Garay, Shay Kutten, and David Peleg.
% \newblock A Sublinear Time Distributed Algorithm for Minimum-Weight Spanning Trees. %SIAM J. Comput. 27(1): 302-316 (1998).

@article{KDOM,
  author    = {Shay Kutten and
               David Peleg},
  title     = {Fast Distributed Construction of Small {\it k}-Dominating
               Sets and Applications},
  journal   = {J. Algorithms},
  volume    = {28},
  number    = {1},
  year      = {1998},
  pages     = {40-66},
  ee        = {http://dx.doi.org/10.1006/jagm.1998.0929},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


%\bibitem{KDOM} Shay Kutten, David Peleg.
%\newblock Fast Distributed Construction of Small k-Dominating Sets and Applications. J. %Algorithms 28(1): 40-66 (1998).

@article{Linial92,
  author    = {Nathan Linial},
  title     = {Locality in Distributed Graph Algorithms},
  journal   = {SIAM J. Comput.},
  volume    = {21},
  number    = {1},
  year      = {1992},
  pages     = {193-201},
  ee        = {http://dx.doi.org/10.1137/0221015},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{kuhn-local,
  author    = {Fabian Kuhn and
               Thomas Moscibroda and
               Roger Wattenhofer},
  title     = {Local Computation: Lower and Upper Bounds},
  journal   = {CoRR},
  volume    = {abs/1011.5470},
  year      = {2010},
  ee        = {http://arxiv.org/abs/1011.5470},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@misc{linial-talk,
  title = {Dijkstra Award talk},
  author = {Nathan Linial},
  year = {Jerusalem, 2013},
  url = {http://www.cs.huji.ac.il/~nati/PAPERS/disc_2013.pdf}
}

%\bibitem:linial-talk}
%Nathan Linial.
%\newblock
%Dijkstra Award talk, EATCS DISC, Jerusalem 2013. http://www.cs.huji.ac.il/~nati/PAPERS/%disc_2013.pdf.

@article{ephremides,
  author    = {Anthony Ephremides and
               Thuan V. Truong},
  title     = {Scheduling broadcasts in multihop radio networks},
  journal   = {IEEE Transactions on Communications},
  volume    = {38},
  number    = {4},
  year      = {1990},
  pages     = {456-460},
  ee        = {http://dx.doi.org/10.1109/26.52656},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


%\bibitem{ephremides}
%Ephremides, Anthony, and Thuan V. Truong.
%\newblock
%Scheduling broadcasts in multihop radio networks. Communications, IEEE Transactions on %38.4 (1990): 456-460.

@article{chlamtac-kutten,
  author    = {Imrich Chlamtac and
               Shay Kutten},
  title     = {Tree-Based Broadcasting in Multihop Radio Networks},
  journal   = {IEEE Trans. Computers},
  volume    = {36},
  number    = {10},
  year      = {1987},
  pages     = {1209-1223},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/TC.1987.1676861},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

%\bibitem{chlamtac-kutten}
%Chlamtac, Imrich, and Shay Kutten.
%\newblock
%On broadcasting in radio networks--problem analysis and protocol design. Communications, %IEEE Transactions on 33.12 (1985): 1240-1246.

@article{d2matching,
  author    = {Hari Balakrishnan and
               Christopher L. Barrett and
               V. S. Anil Kumar and
               Madhav V. Marathe and
               Shripad Thite},
  title     = {The distance-2 matching problem and its relationship to
               the MAC-Layer capacity of ad hoc wireless networks},
  journal   = {IEEE Journal on Selected Areas in Communications},
  volume    = {22},
  number    = {6},
  year      = {2004},
  pages     = {1069-1079},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/JSAC.2004.830909},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
                                                                                                                              

%\bibitem{d2matching}
%Balakrishnan, H., Barrett, C. L., Kumar, V. A., Marathe, M. V., & Thite, S. (2004).
%\newblock The distance-2 matching problem and its relationship to the MAC-layer capacity %of ad hoc wireless networks. Selected Areas in Communications, IEEE Journal on, 22(6), %1069-1079.

@inproceedings{azar-naor-rom,
  author = {Azar, Yossi and Naor, Joseph and Rom, Raphael},
  biburl = {http://www.bibsonomy.org/bibtex/29ca0a2c03265a66c497115d2ccd9f69e/dblp},
  booktitle = {SODA},
  crossref = {conf/soda/1992},
  editor = {Frederickson, Greg N.},
  ee = {http://dl.acm.org/citation.cfm?id=139404.139450},
  interhash = {9ca78c5a00f279de26ce924ac36bff94},
  intrahash = {9ca0a2c03265a66c497115d2ccd9f69e},
  isbn = {0-89791-466-X},
  keywords = {dblp},
  pages = {203-210},
  publisher = {ACM/SIAM},
  timestamp = {2012-12-07T00:00:00.000+0100},
  title = {The Competitiveness of On-Line Assignments.},
  url = {http://dblp.uni-trier.de/db/conf/soda/soda92.html#AzarNR92},
  year = 1992
}



%\bibitem{azar-naor-rom}
%Azar, Y., Naor, J. S., & Rom, R.
%\newblock The competitiveness of on-line assignments. In Proceedings of the third annual %ACM-SIAM symposium on Discrete algorithms (pp. 203-210). Society for Industrial and %Applied Mathematics,  Chicago, 1992, September.

@inproceedings{balanced-minimal,
  author    = {David G. Harris and
               Ehab Morsy and
               Gopal Pandurangan and
               Peter Robinson and
               Aravind Srinivasan},
  title     = {Efficient Computation of Balanced Structures},
  booktitle = {ICALP (2)},
  year      = {2013},
  pages     = {581-593},
  ee        = {http://dx.doi.org/10.1007/978-3-642-39212-2_51},
  crossref  = {DBLP:conf/icalp/2013-2},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

%\bibitem{balanced-minimal}
%Harris, D. G., Morsy, E., Pandurangan, G., Robinson, P., & Srinivasan, A. (2013).
% \newblock Efficient computation of balanced structures. In Automata, Languages, and Programming (pp. 581-593). Springer Berlin Heidelberg.‏


@inproceedings{approx-min-connected,
  author    = {Yuanzhu Peter Chen and
               Arthur L. Liestman},
  title     = {Approximating minimum size weakly-connected dominating sets
               for clustering mobile ad hoc networks},
  booktitle = {MobiHoc},
  year      = {2002},
  pages     = {165-172},
  ee        = {http://doi.acm.org/10.1145/513800.513821},
  crossref  = {DBLP:conf/mobihoc/2002},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

%\bibitem{approx-min-connected} Chen, Y. P., & Liestman, A. L. (2002, June).
%\newblock Approximating minimum size weakly-connected dominating sets for clustering %mobile ad hoc networks. In Proceedings of the 3rd ACM international symposium on Mobile %ad hoc networking & computing (pp. 165-172). ACM.‏


@inproceedings{routing-min-connected,
  author    = {Bevan Das and
               Vaduvur Bharghavan},
  title     = {Routing in Ad-Hoc Networks Using Minimum Connected Dominating
               Sets},
  booktitle = {ICC (1)},
  year      = {1997},
  pages     = {376-380},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

%\bibitem{routing-min-connected} Das, Bevan, and Vaduvur Bharghavan.
% \newblock Routing in ad-hoc networks using minimum connected dominating sets. %Communications, 1997. ICC 97 Montreal,'Towards the Knowledge Millennium'. 1997 IEEE %International Conference on. Vol. 1. IEEE, 1997.‏

@article{localized-cds,
 author = {Dai, Fei and Wu, Jie},
 title = {An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks},
 journal = {IEEE Trans. Parallel Distrib. Syst.},
 issue_date = {October 2004},
 volume = {15},
 number = {10},
 month = oct,
 year = {2004},
 issn = {1045-9219},
 pages = {908--920},
 numpages = {13},
 url = {http://dx.doi.org/10.1109/TPDS.2004.48},
 doi = {10.1109/TPDS.2004.48},
 acmid = {1018316},
 publisher = {IEEE Press},
 address = {Piscataway, NJ, USA},
 keywords = {65, Ad hoc wireless networks, Ad hoc wireless networks, dominant pruning, dominating sets, routing, probabilistic analysis, simulation., dominant pruning, dominating sets, probabilistic analysis, routing, simulation.},
} 

% \bibitem{localized-cds}
% Dai, F., & Wu, J. (2004).
% \newblock An extended localized algorithm for connected dominating set formation in ad %hoc wireless networks. Parallel and Distributed Systems, IEEE Transactions on, 15(10), %908-920.‏

@misc{dijkstra-laudatio,
  title={The 2013 {ACM-EATCS} {E}dsger {W}. {D}ijkstra {P}rize in Distributed Computing, the laudatio.},
  url = {http://www.podc.org/dijkstra/2013-dijkstra-prize/}
}

@inproceedings{KPPRT13:PODC,
  author    = {Shay Kutten and
               Gopal Pandurangan and
               David Peleg and
               Peter Robinson and
               Amitabh Trehan},
  title     = {On the complexity of universal leader election},
  booktitle = {PODC},
  year      = {2013},
  pages     = {100-109},
  ee        = {http://doi.acm.org/10.1145/2484239.2484274},
  crossref  = {DBLP:conf/podc/2013},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{moscibroda-survey,
author = {T. Moscibroda},
title = {Clustering},
journal = {Book Chapter in Algorithms for Sensor and Ad Hoc Networks},
publisher = {Springer},
year = {2007},
pages = {37-60}
}

@article{thurimella,
  author    = {Ramakrishna Thurimella},
  title     = {Sub-Linear Distributed Algorithms for Sparse Certificates
               and Biconnected Components},
  journal   = {J. Algorithms},
  volume    = {23},
  number    = {1},
  year      = {1997},
  pages     = {160-179},
  ee        = {http://dx.doi.org/10.1006/jagm.1996.0832},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{STOC11,
  author    = {Atish Das Sarma and
               Stephan Holzer and
               Liah Kor and
               Amos Korman and
               Danupon Nanongkai and
               Gopal Pandurangan and
               David Peleg and
               Roger Wattenhofer},
  title     = {Distributed Verification and Hardness of Distributed Approximation},
  journal   = {SIAM J. Comput.},
  volume    = {41},
  number    = {5},
  year      = {2012},
  pages     = {1235-1265},
  ee        = {http://dx.doi.org/10.1137/11085178X},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

